package Map;

import java.util.LinkedList;
import java.util.List;

class BinarySearchTreeInsertException extends Exception{

    public BinarySearchTreeInsertException(String message) {
        super(message);
    }
}

public class BinarySearchTree{
    /**
     * 表示二叉树中的节点结构。
     * 该类用于构造二叉树中的节点，包括节点值、左子节点和右子节点。
     */
    static class TreeNode {
        // 节点的值
        public Integer val;
        // 左子节点
        public TreeNode left;
        // 右子节点
        public TreeNode right;

        /**
         * 构造TreeNode类的新实例。
         * 用给定值初始化节点，并且左子节点和右子节点最初为空。
         *
         * @param val 节点值
         */
        public TreeNode(Integer val) {
            this.val = val;
        }
    }
    // 定义二叉搜索树的根节点和大小
    public TreeNode root;
    public Integer size;

    // 无参构造函数，初始化空的二叉搜索树
    public BinarySearchTree(){
        this.size = 0;
        this.root = null;
    }

    // 带参构造函数，用给定值创建一个节点作为二叉搜索树的根
    public BinarySearchTree(Integer val) {
        this.root = new TreeNode(val);
        this.size = 1;
    }

    // 复制构造函数，用一个已存在的二叉搜索树初始化新的二叉搜索树
    public BinarySearchTree(BinarySearchTree tree){
        this.root = tree.root;
        this.size = tree.size;
    }

    /**
     * 在二叉搜索树中搜索指定值
     * @param val 要搜索的值
     * @return 如果找到返回true，否则返回false
     */
    public Boolean search(Integer val){
        TreeNode cur = root;
        while (cur != null){
            if (val > cur.val){
                cur = cur.right;
            }else if(val < cur.val){
                cur = cur.left;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * 在二叉搜索树中插入一个值
     * @param val 要插入的值
     * @return 插入成功返回true，否则返回false
     * @throws BinarySearchTreeInsertException 如果值已存在，则抛出异常
     */
    public Boolean insert(Integer val) throws BinarySearchTreeInsertException {
        if (root == null){
            root = new TreeNode(val);
            this.size = 1;
            return true;
        }
        TreeNode cur = root;
        while (cur != null){
            if (cur.val > val){
                if (cur.right == null){
                    cur.right = new TreeNode(val);
                    this.size++;
                    return true;
                }else {
                    cur = cur.right;
                }
            }else if(cur.val < val){
                if (cur.left == null){
                    cur.left = new TreeNode(val);
                    this.size++;
                    return true;
                }else {
                    cur = cur.left;
                }
            }else {
                throw new BinarySearchTreeInsertException("数据已存在不可插入");
            }
        }
        return false;
    }

    /**
     * 中序遍历二叉搜索树
     * @param root 树的根节点
     * @return 返回中序遍历的结果列表
     */
    public List<Integer> inOrder(TreeNode root){
        List<Integer> list = new LinkedList<>();
        if (root == null){
            return list;
        }
        list.addAll(inOrder(root.left));
        list.add(root.val);
        list.addAll(inOrder(root.right));
        return list;
    }

    /**
     * 插入节点的值（此方法未使用，且逻辑不正确）
     * @param node 要插入值的节点
     * @param val 要插入的值
     * @return 总是返回true
     */
    private Boolean insertVal(TreeNode node, Integer val) {
        node = new TreeNode(val);
        return true;
    }
}
